package com.leetcode2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Index2055platesBetweenCandles {
	
	
	public static void main(String[] args) {
		Index2055platesBetweenCandles candle = new Index2055platesBetweenCandles();
		String s = "***|**|*****|**||**|*";
		int[][] queries = {{1,17},{4,5},{14,17},{5,11},{15,16}};
		int[] ans = candle.platesBetweenCandles(s, queries);
		System.out.println(Arrays.toString(ans));
	}
	
	public int[] platesBetweenCandles(String s, int[][] queries) {
		List<Integer> li = new ArrayList<>();
        int[] answer = new int[queries.length];
        for(int i = 0;i < s.length();i++)
            if(s.charAt(i) == '|') li.add(i);
        int[] memo = new int[li.size()];
        for (int i = 0; i < memo.length; i++) {
			memo[i] = li.get(i);
		}
        for(int i = 0;i < queries.length;i ++){
            int x = queries[i][0],y = queries[i][1];
            int left = leftCandle(memo,x);
            int right = rightCandle(memo,y);
            if(right < left) answer[i] = 0;
            else answer[i] =  memo[right] - memo[left] - (right - left);
        }
        return answer;
    }

    public int leftCandle(int[] nums,int target){
        int left = 0,right = nums.length;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target){
                right = mid ;
            }else if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] == target)
                return mid;
        }
        return left;
    }
    
    public int rightCandle(int[] nums,int target){
        int left = 0,right = nums.length;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target){
                right = mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }
            else if(nums[mid] == target)
                return mid;
        }
        if(right == 0) return 0;
        return right - 1;
    }
}
